Distance Descending Ordering Method: an $O(n)$ Algorithm for Inverting the Mass Matrix in Simulation of Macromolecules with Long Branches

摘要

Fixman's work in 1974 and the follow-up studies have developed a method thatcan factorize the inverse of mass matrix into an arithmetic combination ofthree sparse matrices---one of them is positive definite and need to be furtherfactorized by using the Cholesky decomposition or similar methods. When themolecule subjected to study is of serial chain structure, this method canachieve $O(n)$ computational complexity. However, for molecules with longbranches, Cholesky decomposition about the corresponding positive definitematrix will introduce massive fill-in due to its nonzero structure, which makesthe calculation in scaling of $O(n^3)$. Although several methods have been usedin factorizing the positive definite sparse matrices, no one could strictlyguarantee for no fill-in for all molecules according to our test, and thus$O(n)$ efficiency cannot be obtained by using these traditional methods. Inthis paper we present a new method that can guarantee for no fill-in in doingthe Cholesky decomposition, and as a result, the inverting of mass matrix willremain the $O(n)$ scaling, no matter the molecule structure has long branchesor not.